package acwing._2LanQiao._3Math_DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Project : ProgrammingExercises
 * @Package : ACWing._2LanQiao._3Math_DP
 * @File : Q0002.java
 * @Author : WangRuoyu
 * @Date : 2023/3/14 17:30
 */
// dp空间优化解法
public class Q0002 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String[] words = line.split(" ");
        int N = Integer.parseInt(words[0]);
        int V = Integer.parseInt(words[1]);

        int[] v = new int[N + 1];
        int[] w = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            line = br.readLine();
            words = line.split(" ");
            v[i] = Integer.parseInt(words[0]);
            w[i] = Integer.parseInt(words[1]);
        }

        int[] dp = new int[V + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = V; j >= v[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }

        System.out.println(dp[V]);
    }
}

// dp朴素解法
//public class Q0002 {
//    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        String line = br.readLine();
//        String[] words = line.split(" ");
//        int N = Integer.parseInt(words[0]);
//        int V = Integer.parseInt(words[1]);
//
//        int[] v = new int[N + 1];
//        int[] w = new int[N + 1];
//        for (int i = 1; i <= N; i++) {
//            line = br.readLine();
//            words = line.split(" ");
//            v[i] = Integer.parseInt(words[0]);
//            w[i] = Integer.parseInt(words[1]);
//        }
//
//        int[][] dp = new int[N + 1][V + 1];
//        for (int i = 1; i <= N; i++) {
//            for (int j = 0; j <= V; j++) {
//                dp[i][j] = dp[i - 1][j];
//                if (j >= v[i]) {
//                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
//                }
//            }
//        }
//
////        System.out.println(Arrays.toString(v));
////        System.out.println(Arrays.toString(w));
////
////        for (int i = 0; i <= N; i++) {
////            for (int j = 0; j <= V; j++) {
////                System.out.print(dp[i][j]+" ");
////            }
////            System.out.println();
////        }
////        System.out.println();
//
//        System.out.println(dp[N][V]);
//    }
//}


